package Struct;

import java.util.Arrays;
import java.util.HashMap;

public class UnionSet {
    private HashMap<Integer, Node> indexToNode;

    public UnionSet(int[] nums) {
        Arrays.stream(nums).forEach((o)->{
            Node node = new Node(o);
            node.father = node;
            indexToNode.put(o, node);
        });
    }

    /**
     * 查找能够代表整个集合的那个节点
     * @param node
     * @return
     */
    private Node findFather(Node node){
        Node cur = node;
        while (cur != cur.father) {
            cur = cur.father;
        }
        Node father = cur;

//        下边开始对祖先进行更改，为了以后速度更快
        cur = node;
        while(cur != cur.father){
            Node next = cur.father;
            cur.father = father;
            cur = next;
        }
        return father;
    }

    /**
     * 判断a和b是否在同一集合中
     * @param a
     * @param b
     * @return
     */
    public boolean isSameSet(int a, int b){
        Node aa = indexToNode.get(a);
        Node bb = indexToNode.get(b);

       return findFather(aa) == findFather(bb);
    }

    public void union(int a, int b){
        Node aa = indexToNode.get(a);
        Node bb = indexToNode.get(b);

        if(aa.size > bb.size){
            bb.father = aa;
            bb.size = 0;
        }else{
            aa.father = bb;
            aa.size = 0;
        }
    }

}

class Node{
    public int val;
    public Node father;
    public int size;

    public Node(int val) {
        this.val = val;
        this.size = 1;
    }
}
